package LeetCode.Leet100_199.Leet130_139.Leet139;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/10/11 9:04
 * @Description TODO: 方法一   动态规划（完全背包）  11ms    12.97%
 */
class Solution_1 {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        for (String str : wordDict) {
            set.add(str);
        }
        // 第i次循环，result[i]表示s的[0, i)子串，能否由wordDict中的单词组成
        boolean[] result = new boolean[s.length() + 1];
        result[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // 如果[0, j)能够由wordDict中的单词组成(result[j] == true)，且wordDict中存在[j, i)子串相等的单词
                // 则说明[0, i)能由wordDict中的单词组成
                if (result[j] && wordDict.contains(s.substring(j, i))) {
                    result[i] = true;
                    break;
                }
            }
        }
        return result[s.length()];

    }
}
